package suanfa;

import android.app.Activity;
import android.os.Bundle;
import android.support.annotation.Nullable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 创建时间：2018年01月05日16:35 <br>
 * 作者：fuchaoyang <br>
 * 描述：
 */

public class Test extends Activity {

  @Override protected void onCreate(@Nullable Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    int[] arr = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
    //sort1(arr);
    //System.out.println("arr1 = " + Arrays.toString(arr));
    //sort2(arr);
    //System.out.println("arr2 = " + Arrays.toString(arr));

    quickSort(arr, 0, arr.length - 1);
    System.out.println("arr = " + Arrays.toString(arr));

    List<Integer> list = new ArrayList<>();
    for (int i : arr) {
      list.add(i);
    }
  }

  /**
   * 时间复杂度为O(log2n)
   */
  public static void fun() {
    int t = 1000000; // 语句1
    int i = 1;
    // 循环每次 * 2，即2^f(n)，所以时间复杂度就是log2n
    // 语句2的频度是f(n),则 2^f(n)<=n; f(n)=log2n
    while (i <= t) {
      i *= 2; // 语句2
    }
  }

  /**
   * 快排的时间复杂度最差的是逆序排列的数，j的while循环将不会走。
   * 由于是递归，每次递归都要申请变量，所以复杂度是O(log2n)~O(n)
   */
  public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int i = left, j = right, key = arr[left];

    while (i != j) {
      while (arr[j] >= key && i < j) {
        j--;
      }

      while (arr[i] <= key && i < j) {
        i++;
      }

      // 这段代码执行的次数就是时间复杂度，由于是左右两边同时驱动的，所以该段代码执行的次数平均是n/2次，即2^f(n)
      // 最差就是j的while不走，这段逻辑要循环n次，两次递归，所以是n的平方
      if (i != j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
    arr[left] = arr[i];
    arr[i] = key;

    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
  }

  /**
   * 冒泡：1vs2,2vs3,3vs4，时间复杂度n*n,空间复杂度1，只是操作原来的数组，不需要申请空间
   */
  public static int[] sort1(int[] arr) {
    // 冒泡选择等都只需要一个临时变量，所以空间复杂度是1
    int temp;
    for (int i = 0; i < arr.length; i++) {
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
          temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
        }
      }
    }
    return arr;
  }

  // 选择：从第一个一直往后，找到最大的数，然后第一个数和最大的数交换位置。再从第二个数找后面的最大的数，第二个数和最大的数交换位置，一次
  public static int[] sort2(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      int max = arr[i];
      int position = i;
      for (int j = i; j < arr.length; j++) {
        if (arr[j] > max) {
          max = arr[j];
          position = j;
        }
      }
      // 和最大的数交换位置
      int temp = arr[i];
      arr[i] = arr[position];
      arr[position] = temp;
    }
    return arr;
  }

  /**
   * 合并两个有序数组（如果是无序的，则先对两个数组进行排序）
   * 时间复杂度是 n;
   * 空间复杂度是 n
   * 所谓空间复杂度就是指需要申请新的空间，这里需要创建新的数组，所以为(2)n
   */
  public static int[] merge(int[] arr1, int arr2[]) {
    int[] result = new int[arr1.length + arr2.length];
    int i, j, k; // 用于标记3个数组的index
    i = j = k = 0;
    while (i < arr1.length && j < arr2.length) {
      result[k++] = Math.max(arr1[i++], arr2[j++]);
    }
    while (i != arr1.length) {
      result[k++] = arr1[i++];
    }
    while (j != arr2.length) {
      result[k++] = arr2[j++];
    }

    return result;
  }
}
